import { testSort, measureSort } from "./utils";

function quickSort(arr: number[]) {
  partition(0, arr.length - 1);
  function partition(left: number, right: number) {
    if (left >= right) return;
    // 基准点
    let pivot = arr[right];
    // 两个下标用来分出两边
    let i = left;
    let j = right - 1;

    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }

      while (arr[j] > pivot) {
        j--;
      }

      if (i <= j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
        j--;
      }
    }

    [arr[i], arr[right]] = [arr[right], arr[i]];
    partition(left, j);
    partition(i + 1, right);
  }
  return arr;

}

// 测试
testSort(quickSort);
// 测试时间
measureSort(quickSort, 100000);
